package cn.yiufung.algorithm.search.binary;

/**
 * 二分查找
 * @author 姚锋
 * @createTime 2024年07月04日 11:32:00
 */
public class BinarySearch {

    /**
     * 循环方式二分查找
     * @param arr 需要查询的数组，必须是递增数组
     * @param target 查询目标
     * @return 目标索引，若查不到返回-1
     */
    public static int loopBinarySearch(int[] arr, int target){
        if(arr == null){
            return -1;
        }
        int l = 0, r = arr.length-1;
        while(l <= r){
            int mid = (l+r) >>> 1;
            if(arr[mid] < target){
                l = mid + 1;
            }else if(arr[mid] > target){
                r = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    /**
     * 递归方式二分查找
     * @param arr 需要查询的数组，必须是递增数组
     * @param target 查询目标
     * @param l 左边界
     * @param r 右边界
     * @return
     */
    public static int recursionBinarySearch(int[] arr, int target, int l, int r){
        if(arr == null || l < 0 || r >= arr.length || l > r){
            return -1;
        }
        int mid = (l+r) >>> 1;
        if(arr[mid] < target){
            return recursionBinarySearch(arr, target, mid + 1, r);
        }else if(arr[mid] > target){
            return recursionBinarySearch(arr, target, l, mid - 1);
        }else{
            return mid;
        }
    }

    /**
     * 循环平衡二分查找算法
     * @param arr 需要查询的数组，必须是递增数组
     * @param target 查询目标
     * @return 目标索引，若查不到返回-1
     */
    public static int loopBinarySearchBalance(int[] arr, int target){
        if(arr == null || arr.length == 0){
            return -1;
        }
        int l = 0, r = arr.length;
        while(l < r - 1){
            int mid = (l+r) >>> 1;
            if(arr[mid] > target){
                r = mid;
            }else {
                l = mid;
            }
        }
        if(arr[l] == target){
            return l;
        } else {
            return -1;
        }
    }

}
